package Verifier.ByteTree;

import java.util.LinkedList;
import java.util.List;

/**
 * <pre>
 * ***************************
 * IMPORTANT! READ THIS FIRST:
 * ===========================
 * 
 * a.	By "byte string" we denote the string that represents the object for example: 
 * 		"000000000200000000020100000001AF010000000203E101000000022D52"
 * 
 * b. 	By "byte array" we denote the byte array representation of the byte string where every
 * 		two chars are becoming one byte.
 * 
 * c.	By "ByteTree" we denote the data structure that is built according to the byte array/string
 * 		that were given in the constructor.	The data is stored as a tree.
 * 
 * d.	When using the word data with any of the above we denote the corresponding representation
 * 		for the data of the leaf only and without the prefix of "01" and the number that follows.
 *</pre>
 *
 * @author ofekp
 */
public class ByteTree {
	private static final int Leaf_Value = 1;
	private static final int Node_Value = 0;
	private static final int Unknown_Value = -1;
	private static final int Num_Bytes_Per_DataLength = 4;
	private static final int Num_Chars_Per_Byte = 2;
	private static final int Hexa_Base = 16;
	
	private Node root = new Node(null);
	private String byteString = "";
	private byte[] byteArray = null;
	private static final boolean OUTPUT_ENABLE = false;
	
	// Next fields are built when calling the byte string 
	// parser function "parseByteTreeString"
	public String viewableString = ""; //for example: "Node(Node(Leaf("af")Leaf("03e1"))Leaf("2d52"))"
	public List<Leaf> leafDataList = new LinkedList<Leaf>();
	
	/**
	 * @param byteString a string from which to create a ByteTree
	 */
	public ByteTree(String byteString) {
		this.byteString = byteString.toLowerCase();
		parseByteTreeString(byteString, root);
		byteArray = byteStringToByteArray(byteString);
		
		isValid();
	}
	
	/**
	 * @param bArr the byte array representation of an object
	 */
	public ByteTree(byte[] bArr) {
		byteArray = bArr;
		byteString = byteArrayToByteString(bArr);
		parseByteTreeString(byteString, root);
		
		isValid();
	}
	
	/**
	 * @param elem a node or a leaf to become the ByteTree.
	 */
	public ByteTree(ByteTreeElement elem) {
		root.addElement(elem);
		elem.setParent(root);
		
		byteString = generateByteString();
		parseByteTreeString(byteString, root);
		byteArray = byteStringToByteArray(byteString);
		
		isValid();
	}
	
	/**
	 * @param b the current string to parse as byte string.
	 * @param node the current node.
	 * @return   <pre>
	 * 			 a.	leafDataList is updated with all the leafs' data
	 * 				in order from left to right.
	 * 
	 * 			 b.	viewableString is updated.
	 * 				example: "Node(Node(Leaf("af")Leaf("03e1"))Leaf("2d52"))"
	 * 				
	 * 			 c.	The ByteTree data structure is built in the form of a tree
	 * </pre>
	 * @throws Exception 
	 * @pre		root was uninitialized using "root = new Node(null)".
	 * @pre		viewableString = "".
	 * @pre 	leafDataList = new LinkedList<Leaf>().
	 */
	private String parseByteTreeString(String b, Node node) {
		//System.out.println(b);
		int isLeafVal = isLeafNext(b);
		if (isLeafVal == Unknown_Value) {
			if (OUTPUT_ENABLE)
				System.out.println("Error: Expected leaf or node were currupt. Could not build ByteTree");
			return null;
		}
		if (isLeafVal == Leaf_Value) {
			// next ByteTree element is a leaf
			b = b.substring(Num_Chars_Per_Byte); // jump over the type of the node, which is a leaf
			int numOfDataBytes = 0;
			numOfDataBytes = getLengthOfData(b);
			b = b.substring(Num_Bytes_Per_DataLength * Num_Chars_Per_Byte);
			byte[] bArr = getLeafData(b, numOfDataBytes);
			b = b.substring(numOfDataBytes * Num_Chars_Per_Byte);
			Leaf newLeaf = new Leaf(bArr, node);
			node.addElement((ByteTreeElement) newLeaf);
			leafDataList.add(newLeaf);
			
			viewableString += "Leaf(\"";
			viewableString += newLeaf.getDataByteString();
			viewableString += "\")";
			
			return b;
		} else {
			// next ByteTree element is a node
			b = b.substring(Num_Chars_Per_Byte); // jump over the type of the node
			int numOfElements = 0;
			numOfElements = getLengthOfData(b);
			b = b.substring(Num_Bytes_Per_DataLength * Num_Chars_Per_Byte);
			Node newNode = new Node(node);
			node.addElement(newNode);
			viewableString += "Node(";
			for (int i = 0; i < numOfElements ; i++) {
				b = parseByteTreeString(b, newNode);
			}
			viewableString += ")";
			return b;
		}
	}
	
	/**
	 * This function will return the data in the leaf found in the index
	 * 'index' as a byte string.
	 * @param index The index of the requested leaf starting from 0.
	 * @return	the byte string contained in the requested leaf. 
	 */
	public String getLeafDataByteStringByIndex(int index) {
		return leafDataList.get(index).getDataByteString();
	}
	
	/**
	 * This function will return the data in the leaf found in the index
	 * 'index' as a byte array.
	 * @param index The index of the requested leaf starting from 0.
	 * @return	the byte array contained in the requested leaf.
	 */
	public byte[] getLeafDataByteArrayByIndex(int index) {
		return leafDataList.get(index).getDataByteArray();
	}
	
	/**
	 * @return The number of leafs in the ByteTree.
	 */
	public int getNumOfLeafs() {
		return leafDataList.size();
	}
	
	/**
	 * This function will return the actual root of the ByteTree which can be
	 * either a node or a leaf (ByteTreeElement).
	 * 
	 * @return the first ByteTreeElement which is the only child of 'root'.
	 */
	public ByteTreeElement getFirstByteTreeElement() {
		return root.getChild(0);
	}
	
	/**
	 * <pre>
	 * This function will convert this ByteTree to a byte string while not using the 
	 * 'byteString' field generated with the constructor
	 * NOT USING THE 'byteString' FIELD! </pre>
	 *
	 * @return 	the byte string representation of this ByteTree
	 * 			Example: "000000000200000000020100000001AF010000000203E101000000022D52"
	 */
	public String generateByteString() {
		return root.getChild(0).toByteString();
	}
	
	/**
	 * @return	The full string representation of this ByteTree instance
	 * 			Example: "000000000200000000020100000001AF010000000203E101000000022D52"
	 */
	public String getByteString() {
		return this.byteString;
	}
	
	/**
	 * @return	The full string representation of this ByteTree instance
	 * 			Example: "000000000200000000020100000001AF010000000203E101000000022D52"
	 */
	public byte[] getByteArray() {
		return this.byteArray;
	}
	
	/**
	 * Returns a representative string for the byte-tree.
	 * Pre-condition: the construction had been successful.
	 * 
	 * @return 	the representation of this ByteTree as shown in the spec.
	 * 			Example: "Node(Node(Leaf("af")Leaf("03e1"))Leaf("2d52"))"
	 */
	public String toString() {
		return viewableString;
	}
	
	/**
	 * This function will check the validity of the data structure.
	 * 
	 * @return the index of the problem that failed or 0 if all succeeded.
	 */
	@SuppressWarnings("unused")
	public boolean isValid() {
		int numOfTests = 3;
		boolean index[] = new boolean[numOfTests];
		
		// test 1
		// first, check that the byte string we have generated while creating the physical tree is the same as the generated from the tree
		if (byteString.compareTo(this.generateByteString()) != 0) {
			if (OUTPUT_ENABLE) {
				System.out.println("==> " + byteString);
				System.out.println("==> " + this.generateByteString());
			}
			index[0] = true;
		}
		
		// test 2
		boolean b_temp = true;
		// second, check that the byte array which can be generated from the string is the same as we created
		byte[] bArr_temp = byteStringToByteArray(byteString);
		for (int i = 0; i < byteArray.length; i++) {
			if (byteArray[i] != bArr_temp[i]) {
				b_temp = false;
			}
		}
		if (!b_temp) {
			index[1] = true;
		}
		
		// test 3
		// thirdly, check that all the variables we created aren't empty for some reason
		if (byteString == null || root.getDataLength() == 0
				|| byteArray == null || viewableString == ""
				|| leafDataList.size() == 0)
			index[2] = true;
		
		// print errors if any exists
		
		
		// now, check which tests have failed and return the result of all the tests
		int i = 0;
		boolean res = true;
		for (boolean b : index) {
			res = res && b;
			if (b && OUTPUT_ENABLE)
				System.out.println("Error: ByteTree not valid. Test number " + (i + 1) + " has faild.");
			i++;
		}
		
		return res;
	}
	
	
	
	//***************************************************************
	//						static functions
	//===============================================================
	
	/**
	 * Used in the constructor.
	 * The function will transform a byte array to a hex string where.
	 * every two chars representing a byte from the byte array.
	 * @param dataByteArray the byte array to convert to byte string.
	 * @return the byte string represented by dataByteArray.
	 */
	public static String byteArrayToByteString(byte[] dataByteArray) {
		String str = "";
		for (byte d : dataByteArray) {
			str += byteToTwoChars(d);
		}
		return str;
	}
	
	/**
	 * <pre>
	 * Used in 'byteArrayToString' function.
	 * The function will transform a byte to two hex chars.
	 * The opposite function was also implemented.
	 * </pre>
	 * @param b the byte to convert.
	 * @return 	the hex string that that byte is representing, the length.
	 * 			of the string is 2.
	 */
	private static String byteToTwoChars(byte b) {
		int bh = b >> 4; // get the high 4 bits
		int bl = (b << 4) >> 4; // get the low 4 bits
		String sh = Integer.toHexString(bh);
		char ch = sh.charAt(sh.length() - 1);
		String sl = Integer.toHexString(bl);
		char cl = sl.charAt(sl.length() - 1);
		return String.valueOf(ch) + String.valueOf(cl);
	}
	
	/**
	 * Used in 'parseByteTreeString' function.
	 * 
	 * @param b a substring of a ByteTree representation.
	 * @param length the length in Bytes to be extracted from b.
	 * @return the byte array represented by the prefix of the string b.
	 * @pre the string b prefix is the beginning of the data of a leaf.
	 */
	private static byte[] getLeafData(String b, int length) {
		
		// Need to extract 2*length chars from the string b because: (2 chars) = (1 byte)
		byte[] bArr = new byte[length];
		String strData = null;
		
		try {
			strData = b.substring(0, Num_Chars_Per_Byte * length);
		} catch (IndexOutOfBoundsException i) {
			if (OUTPUT_ENABLE)
				System.out.println("Error: Hex data string was too short. b = " + b + ". Need " + length + " bytes");
			i.printStackTrace();
			return null;
		}
		
		for (int i = 0; i < length; i++) {
			bArr[i] = (byte) Integer.parseInt(strData.substring(0, Num_Chars_Per_Byte), Hexa_Base);
			strData = strData.substring(Num_Chars_Per_Byte); // remove the chars we already read
		}
		
		return bArr;
	}
	
	/**
	 * Used in 'parseByteTreeString' function.
	 * Currently max number to parse is 0x7fffffff.
	 * @param b a substirng of the byte string representation.
	 * @return
	 */
	private static int getLengthOfData(String b) {
		String strVal = null;
		int intVal = 0;
		
		try {
			strVal = b.substring(0, 8);
		} catch (IndexOutOfBoundsException i) {
			if (OUTPUT_ENABLE)
				System.out.println("Error: Hex String was too short. b = " + b);
			i.printStackTrace();
			return 0;
		}
		//System.out.println("strVal = " + strVal);
		try {
			intVal = Integer.parseInt(strVal, Hexa_Base);
		} catch (NumberFormatException n) {
			if (OUTPUT_ENABLE)
				System.out.println("Error: Hex String was corrupted. strVal = " + strVal);
			n.printStackTrace();
			return 0;
		}
		
		return intVal;
	}	
	
	/**
	 * Used in 'parseByteTreeString' function.
	 * 
	 * @param prefix the prefix 00 or 01 other wise.
	 * @return - true if prefix = "01".
	 */
	private static int isLeafNext(String b) {
		try {
			// read the first byte from the hex string
			int val = Integer.parseInt(b.substring(0, Num_Chars_Per_Byte));
			if (val != Node_Value && val != Leaf_Value) {
				if (OUTPUT_ENABLE)
					System.out.println("Error: Prefix of leaf/node not 01 or 00, val=" + val);
				return Unknown_Value;
			}
			return (val == Leaf_Value ? Leaf_Value : Node_Value);
		} catch(NumberFormatException n) {
			if (OUTPUT_ENABLE)
				System.out.println("Error: Prefix of leaf/node was corrupted");
			n.printStackTrace();
			return Unknown_Value;
		}
	}
	
	/**
	 * This function will convert a byte string to a byte array.
	 * @param byteString the byte string to convert.
	 * @return 	the byte array represented by the given string.
	 * 			the length of the array is (str.length() / 2).
	 */
	public static byte[] byteStringToByteArray(String byteString) {
		int len = byteString.length();
		if (len % Num_Chars_Per_Byte != 0) {
			if (OUTPUT_ENABLE)
				System.out.println("Error: A byte string of an odd length cannot be converted to byte array.");
			return null;
		}
		int numOfBytes = (len / Num_Chars_Per_Byte);
		byte[] res = new byte[numOfBytes];
		String nextString = "";
		for (int i = 0; i < numOfBytes; i++) {
			nextString = byteString.substring(0, Num_Chars_Per_Byte);
			byteString = byteString.substring(Num_Chars_Per_Byte);
			try {
				res[i] = twoCharsToByte(nextString);
			} catch (Exception e) {
				e.printStackTrace();
				res[i] = -1;
			}
		}
		return res;		
	}
	
	/**
	 * <pre>
	 * This function will turn two hex chars to a byte.
	 * The opposite function was also implemented.
	 * </pre>
	 * @param str the string that contains the two hex chars
	 * @return the byte that is represented by the two given chars
	 * @throws Exception
	 */
	private static byte twoCharsToByte(String str) throws Exception {
		if (str.length() != Num_Chars_Per_Byte) {
			throw new Exception("Error: Only a string of length 2 can be converted to a byte");
		}
		
		char a = str.charAt(0);
		char b = str.charAt(1);
		if (!isHexChar(a) || !isHexChar(b)) {
			throw new Exception("Error: The string \"" + str + "\" contains non hex chars. Cannot convert to byte.");
		}
		
		byte res = 0;
		
		// get low bits
		if (b >= '0' && b <= '9')
			res = (byte) (res | (b - 48));
		else if (b >= 'a' && b <= 'f')
			res = (byte) (res | (b - 97 + 10));
		else
			res = (byte) (res | (b - 65 + 10));
		
		// get high bits
		byte temp = 0;
		if (a >= '0' && a <= '9')
			temp = (byte) (temp | (a - 48));
		else if (a >= 'a' && a <= 'f')
			temp = (byte) (temp | (a - 97 + 10));
		else
			temp = (byte) (temp | (a - 65 + 10));
		
		temp <<= 4;
		res |= temp;
		
		return res;
	}
	
	/**
	 * @param c a char
	 * @return true is that char is a hex digit, flase otherwise
	 */
	private static boolean isHexChar(char c) {
		if (c >= '0' && c <= '9')
			return true;
		if (c >= 'a' && c <= 'f')
			return true;
		if (c >= 'A' && c <= 'F')
			return true;
		return false;
	}
	
	
	/**
	 * This is the inverse function of the function 'parseLeafAsString'.
	 * This function will represent the string str as a byte string,
	 * meaning a hex string that is a leaf containing the requested string. 
	 * @param str a string to be converted to a ByteTree representation
	 * @return 	<pre>The ByteTree representation of the string str.
	 * 			leaf(char(0).hex|char(1).hex|...|char(n).hex) is returned where
	 * 			char(i).hex is the i'th char of str in 2 char hex representation.
	 * 			</pre>
	 *  
	 */
	public static String strToByteString(String str) {
		String resStr = "01";
		
		String numOfBytes = Integer.toHexString(str.length());
		int len = numOfBytes.length();
		
		for (int i = 0; i < (8 - len); i++) {
			numOfBytes = '0' + numOfBytes;
		}
		resStr += numOfBytes;
		
		for(int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);
			String cHex = Integer.toHexString(c);
			resStr += cHex;
		}
		return resStr;
	}
	
	/**
	 * This is the inverse function of the function 'strToByteString'.
	 * Every two chars in the leaf's data are considered one byte and so 
	 * generate one char.
	 * @param bt a ByteTree
	 * @param leafIndex - the index of the Leaf starting with 0.
	 * @return 	the data inside the leaf in the requested index from the 
	 * 			ByteTree bt as if it were a string.
	 */
	public static String parseLeafAsString(ByteTree bt, int leafIndex) {
		String nextChar;
		String resStr = "";
		String data = bt.getLeafDataByteStringByIndex(leafIndex);
		int len = data.length() / Num_Chars_Per_Byte;
		for (int i = 0; i < len; i++) {
			nextChar = data.substring(0, Num_Chars_Per_Byte);
			data = data.substring(Num_Chars_Per_Byte);
			int charVal = Integer.valueOf(nextChar, Hexa_Base);
			resStr += String.valueOf(Character.toChars(charVal));
		}
		return resStr;
	}
}